/* 
 * Raj Akula
 * Finds maximum profit possible from a set a of projects in the file Proj4Data.txt
 * Constraints are hard coded into the program. 
 *
 */


#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>
#include <map>
#include <exception>
#include <cstdio>
using namespace std;

//typedef for Money and Labor
typedef unsigned int Money;
typedef unsigned int Labor;


// Requirements class for project requirements as well as overall resource availability
class Requirements
{	
public:
	//set this to be public for efficency and for ease of use for coding probably not good coding methods should 
	//have getter and setter methods for this... 
	Money liquidity;
	Labor officeWork;
	Labor programmingWork;
	
	//Need this as default constructor... 
	Requirements(){}

	//setting the fields to the passed in values
	Requirements(Money liquidity, Labor officeWork, Labor programmingWork)
	{
		this->liquidity = liquidity;
		this->officeWork = officeWork;
		this->programmingWork = programmingWork;
	}
	
	//Used for storing in the map
	bool operator<(const Requirements & rhs)const
	{
		if (this->liquidity < rhs.liquidity)
			return true;
		if (this->liquidity > rhs.liquidity)
			return false;
		if (this->officeWork < rhs.officeWork)
			return true;
		if (this->officeWork > rhs.officeWork)
			return false;
		if (this->programmingWork < rhs.programmingWork)
			return true;
		if(this->programmingWork > rhs.programmingWork)
			return false;		
		return false; 
	}
	
	//Needed when subtracting requirements
	Requirements & operator-=(const Requirements & rhs)
	{
 			this->liquidity -= rhs.liquidity;
			this->officeWork -= rhs.officeWork; 
			this->programmingWork -= rhs.programmingWork;
			return *this;
	}

	//calls -= and does same thing just put in for ease of use
    Requirements operator-(const Requirements & rhs)
	{
			Requirements temp = *this;
			temp -= rhs;
			return temp;
	}
	
	//Used for print statement when i need to print out the requirements
	void print(ostream & out) const 
	{
		out << this->liquidity << "   " << this->officeWork << "   " << this->programmingWork;
	}
};

//Class for projects
class Projects {
private:
	// These are private where as the other ones aren't because no project costs will ever change
	// for our purposes...
	string name;
	Requirements requirements;
	Money profit;

public:
	//Initilizing the projects...
	Projects(string name, Requirements requirements, Money profit)
	{
		this->name = name;
		this->requirements = requirements;
		this->profit = profit;
	}

	// Used for printing the projects once they are chosen... 
	void print(ostream & out) const 
	{
		out << this->name << "   ";
		this->requirements.print(out);
		out << "   " << this->profit;
	}
	
	//getter methods...
	string getName()
	{
		return this->name;
	}

	Requirements getRequirements()
	{
		return this->requirements;
	}

	Money getProfit()
	{
		return this->profit;
	}
};

//Used for printing Projects 
ostream & operator<<(ostream & out, const Projects & project)
{
	project.print(out);
	return out;
}

//Type for value map
typedef map<pair<Requirements, size_t>, pair<Money, bool> > ValueMap;

Money bestProfit(vector<Projects> & projects, Requirements & requirements, ValueMap & valueMap, size_t n)
{
	//Needed if size of project pool is 0 then 0
	if(n==0)
		return 0;

	//Iterator to iterate through value map to find with same requirements and with size n
	ValueMap::iterator itr = valueMap.find(make_pair(requirements, n));
	
	//In case it isn't found then solve this... 
	if(itr != valueMap.end())
	{
		return itr->second.first;
	}

	//Best one is the same requirements with one less projects
	Money best1 = bestProfit(projects, requirements, valueMap, n - 1);
	//Best two is 0 if the project requirements exceed the available resources
	Money best2 = 0;
	
	// if you have enough resources then see what the value is if you take the project
	if((projects[n-1].getRequirements().liquidity <= requirements.liquidity) && (projects[n-1].getRequirements().officeWork <= requirements.officeWork) && (projects[n-1].getRequirements().programmingWork <= requirements.programmingWork))
		best2 = bestProfit(projects, requirements - projects[n - 1].getRequirements(), valueMap, n - 1) + projects[n - 1].getProfit();
	
	//Take the one and put in the value map... 
	if(best1 >= best2)
	{ 
		valueMap.insert(make_pair (make_pair( requirements, n), make_pair(best1, false)));
		return best1;
	}
	else
	{
		valueMap.insert(make_pair (make_pair (requirements, n), make_pair(best2, true)));
		return best2;
	}
}

// This is a recursive method to get all teh best profits.. 
vector<Projects> getBestProjects(vector<Projects> & projects, Requirements & requirements, ValueMap & valueMap, size_t n, vector<Projects> & best)
{
	if(n!=0) 
	{	
		ValueMap::iterator itr= valueMap.find(make_pair(requirements,n));
		if(itr != valueMap.end())
			if(itr->second.second)
			{
				best.push_back(projects[n - 1]);
				getBestProjects(projects, requirements - projects[n - 1].getRequirements(), valueMap, n - 1, best);
			}
		else
			getBestProjects(projects, requirements, valueMap, n - 1, best);
	}
	return best;
}

//Setup for printing available resources
void printAvailable(Requirements & requirements)
{
	cout << "Available resources -" << endl;
	cout << "\t Liquidity: " << requirements.liquidity << endl;
	cout << "\t Office Work: " << requirements.officeWork << endl;
	cout << "\t Programing Work: " << requirements.programmingWork << endl << endl;
}

// This is my main method first it find best profits then prints available resources and 
// then looks in the map to see which projects which gave the best profit overall
void reportBestProfit(vector<Projects> & projects, Requirements & requirements) 
{
	//For calculating best value
	Labor officeWork = 0;
	Money liquidity = 0;
	Labor programmingWork = 0;
	ValueMap valueMap;

	//Gets best profit
	Money profit = bestProfit(projects, requirements, valueMap, projects.size());

	//Printing available resources
	printAvailable(requirements);

	//Gets what projects got the best profit...
	vector<Projects> best;
	best = getBestProjects(projects, requirements, valueMap, projects.size(), best);
	cout << "Selected Projects -" << endl << endl;

	//Pritns all the selected projects does it in reverse order because my getBest Projects does it in reverse order... 
	for(vector<Projects>::reverse_iterator iter = best.rbegin(); iter < best.rend(); iter++)
	{ 
		cout << "\t " << *iter << endl;
		liquidity += iter->getRequirements().liquidity;
		officeWork += iter->getRequirements().officeWork;
		programmingWork += iter->getRequirements().programmingWork;
	}

	//Prints all resouces used... 
	cout << endl << "Total resources used -" << endl;
	cout << "\t Liquidity: " << liquidity << endl;
	cout << "\t Office Work: " << officeWork << endl;
	cout << "\t Programming Work: " << programmingWork << endl << endl;
	cout << "Profit: " << profit << endl;
}

class IO_Exception : public runtime_error
{
public:
	IO_Exception(const string & message) : runtime_error(message) { }
};

void readProjects(vector<Projects> & projects, const string & fileName)
{
	ifstream infile(fileName.c_str());
	if (!infile)
		throw IO_Exception("Could not open " + fileName);
	string oneLine;
	unsigned int lineNum = 0;
	while (getline(infile, oneLine))
	{
		istringstream st(oneLine);
		lineNum++;
		string name;
		Money liquidity;
		Labor officeWork;
		Labor programmingWork;
		Money profit;
		st >> name;
		st >> liquidity;
		st >> officeWork;
		st >> programmingWork;
		st >> profit;
		if (st.fail())
		{
			cerr << "Skipping line number " << lineNum << ": "
				 << oneLine << endl;
			continue;
		}
		string junk;
		if (st >> junk)
		{
			cerr << "Skipping line number " << lineNum << ": "
				 << oneLine << endl;
			continue;
		}

		projects.push_back(Projects(name, Requirements(liquidity, officeWork, programmingWork), profit));
	}

	if (!infile.eof())
		throw IO_Exception("Error reading from " + fileName);
}

int main()
{
	vector<Projects> projects;
	try
	{
		readProjects(projects, "Proj4Data.txt");
	}
	catch (const IO_Exception & ex)
	{
		cerr << "IO error from: " << ex.what() << endl;
		return 1;
	}
	reportBestProfit(projects, Requirements(400, 900, 2000));
	
	return 0;
}